package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname RadixSort
 * @Project Data-structure-and-algorithm
 * @Description 基数排序：
 * 基数排序(radix sort）属于“分配式排序”( distribution sort），又称“桶子法”(bucket sort）或bin sort，
 * 顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶（一维数组）”中，达到排序的作用
 * 实现:将整数按位数切割成不同的数字，然后按每个位数分别比较。
 * @Author wpcheng
 * @Create 2021-08-10-8:56
 * @Version 1.0
 */
public class RadixSortPlus {
    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        System.out.println("排序后为"+Arrays.toString(arr));

    }

    public static void radixSort(int[] arr) {

        //得到数组中最大数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]){
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        /*根据最大数的为数来确定有几轮排序
         * 创建一个二维数组int[10][arr.length]：
         * 10表示10个一维数组，也就是10个桶，分别为0-9;arr.length表示每个桶可以存放数的最大个数
         * 对每个数的个位数进行排序后，按个位数大小分别放入与下标对应的桶
         * */
        int[][] bucket = new int[10][arr.length];
        //记录每个桶放了多少个数,如bucketElementCounts[1] 放的就是下标为1的桶里数的个数
        int[] bucketElementCounts = new int[10];

        for (int i = 0  ,n = 1 ; i < maxLength; i++,n*=10) {
            //对每个数的位数进行排序,第一次是个位，第二次是十位，第三次是百位……
            for (int j = 0; j < arr.length; j++) {
                //得到每个数的第几次排序对应的位数
                int digitOfElement = arr[j] / n % 10;
                //根据个位数放入对应的桶 [digitOfElement]表示放入第几个桶，[bucketElementCounts[digitOfElement]]表示当前桶存放数的个数
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //把桶里的数放回数组
            int index = 0; //初始化数组下标
            //循环所有的桶
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    //循环第k个桶
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //每循环完一个桶，就把该桶置为0，方便下次遍历
                bucketElementCounts[k] = 0;
            }

        }

    }

}
